package org.regotto.basics.graph;

import org.regotto.common.Utils;

import java.util.Scanner;

/**
 * 基础版 djk, 求最短路
 */
public class DjkBase {

    static final int N = 100;
    static int[][] g = new int[N][N];
    static int[] dis = new int[N], st = new int[N];
    static int n, m;

    static int djk() {
        Utils.full(dis, 0x3f3f3f3f);
        dis[1] = 0;
        for (int i = 0; i < n; i++) {
            int t = -1;
            for (int j = 1; j <= n; j++) {
                if (st[j] == 0 && (t == -1 || dis[t] > dis[j])) t = j;
            }
            st[t] = 1;
            for (int j = 1; j <= n; j++) {
                dis[j] = Math.min(dis[j], dis[t] + g[t][j]);
            }
        }
        return dis[n] == 0x3f3f3f3f ? -1 : dis[n];
    }

    public static void main(String[] args) {
        Utils.full(g, 0x3f3f3f3f);
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        for (int i = 0; i < m; i++) {
            int a = sc.nextInt(), b = sc.nextInt(), c = sc.nextInt();
            g[a][b] = Math.min(g[a][b], c);
        }
        System.out.println(djk());
    }

}
